#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: graph_num.py 
@version:
@time: 2024/01/26

每个图案都是由1组成的一个区域，不同图案之间由0相互阻隔。
遍历给定的二维数组，当检测到元素1时，以该节点为起点进行深度优先搜索，
该过程类似图的遍历。只要发现一个新的起点，就一定有一个新的图案，
在遍历二维数组的过程中需要避免对一个节点重复访问，因此需要用另外一个维度相同的二维
数组来记录每个节点是否被访问过，遍历过程照顾你发现为1的元素已经被访问过，
则跳过该节点。可见深度优先搜索是非常明智的解决方法，沿着值为1的路径一直
走到不能再走，则停止该过程。
"""


class Pattern:
    length = 0
    width = 0
    directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    marked = []

    def graph_num(self, grid):
        self.length = len(grid)
        if self.length == 0:
            return 0
        self.width = len(grid[0])
        self.marked = [[0 for _ in range(self.width)] for _ in range(self.length)]
        res = 0
        for i in range(self.length):
            for j in range(self.width):
                if self.marked[i][j] == 0 and grid[i][j] == 1:
                    res += 1
                    self.dfs(grid, i, j)
        return res

    def dfs(self, grid, i, j):
        self.marked[i][j] = 1
        for direction in self.directions:
            new_i = i + direction[0]
            new_j = j + direction[1]
            if 0 <= new_i < self.length \
                    and 0 <= new_j < self.width \
                    and self.marked[new_i][new_j] == 0 \
                    and grid[new_i][new_j] == 1:
                self.dfs(grid, new_i, new_j)


Grid1 = [
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [1, 1, 1, 0, 0]
]
Grid2 = [
    [1, 1, 0, 1, 0],
    [1, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [1, 1, 0, 0, 0]
]
print(Pattern().graph_num(Grid1))
print(Pattern().graph_num(Grid2))
